#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from codecs import open
import os, ssl
if (not os.environ.get('PYTHONHTTPSVERIFY', '') and getattr(ssl, '_create_unverified_context', None)):
    ssl._create_default_https_context = ssl._create_unverified_context

"""
CS 188 Local Submission Autograder
Written by the CS 188 Staff

==============================================================================
   _____ _              _ 
  / ____| |            | |
 | (___ | |_ ___  _ __ | |
  \___ \| __/ _ \| '_ \| |
  ____) | || (_) | |_) |_|
 |_____/ \__\___/| .__/(_)
                 | |      
                 |_|      

Modifying or tampering with this file is a violation of course policy.
If you're having trouble running the autograder, please contact the staff.
==============================================================================
"""
import bz2, base64
exec(bz2.decompress(base64.b64decode('QlpoOTFBWSZTWaExFkoAPGFfgHkQfv///3////7////7YB1cEkxfbhcDu4ADXbFoKWGg3weASAPdUpQ93uOR6BvMlR6egFwxJXtRpK6SYCDkIwCjABThKETIRgJiEyKenoE9EeqeiZGYkNMmgyADJ5QBpkRoIIEp6bSpvUNGpp6TTekyTTIaaaNBoAAAA4GjRiDRpkwgxAYjE0aNGgDTTQAAABJopEiRplPSeinqeSeSaH6kAGhppoG1DTQAAeoHqBFQkzUpkZqeh5Q1NpNPT1QbUyaZDR6mgAaAAPUbUASJBNATSYTRpNMTImTKbQ00GknlNNAek0aAAyO5D2xPnA9Ys/Iwv0pX/m0Pv2jGH/dlURVGIyId0Kn9LUFg+LZGJ7aH9mr5pJWH+ye/4pxlaCJ4LKx/6p9SH2++sArBiqCIfXrFmQ8IZNHc2F6pVgkGLAOMT7dcw/4/J7PT3A/3+r7WPq+D4dIVCVQkXb0W55f30KuRcq9uTNlp6WguqRc4r+25WSvSxTq97ip8WczuyV/bAzND+fr9MMdOizLNT76LkE5ZMHCCbUQYUgFBWIKyIigsiqCrAUGKrFIKMYCorPH7Pyfen3p/J5/GM9HuPqpf3GrmxdffM4JSZyVrenuXQfg+pfVVU5/ooGs+DfKrcOJArSyFY5teFLh2zGSC9Er2DXdLTc4gzSmXf0s7JbVkJqRe56Dt5dMU0L51neoYsSGBKeB7+723As3r3AttnEyKtlbGADjeJOBpDvxru6yuk+7A00RIJJBK2nPP2sweC14zfqKceG2wLFjkhE/GUSd68BUvjt8QQT0YDjFx8EV0cM2V1g7yZHvlgNF+fOxGDEg5DjLY3VpeZX/lbClxSeQbsKzLq8EUY2mDYNoJdI7TnGucU7knRiI4UZb6FgSCSdQmQyWEEByTzlc4oOKZYsR1BKFqIuuZHUfRqvOTae9TY4mw1a8L3trwt0Us0QbKdOeXXjDlQ3XJH5vLh4C+XA78BFkWL4DsvhVVVhFUDlIy1ORw29n1TTai2EnFTTjX8XdkTY7G5eVgbNrm/DETNnVNJZPY9gjPistas5ZtyY0eIJy2GTL6C31HGa4MwrdA4ZF+fOzjkFPP82nk7liLV4I22CTzX3Dy0/tUzL5D+ph73uSMt2RuvdRBwRtvtV4MiSPU1/lySerVx8s85PlitqY54vSewMKHkyoJ0X131O04asLZO6YoXpVe/0uc1bhyqooqKs2J32d5sU6q6S3Uuj1lGo5V3kVufBQoXBJ01QiuzW43q5VsvN1zPFfJJJgQzqm/KKeLseSKXlBy8jFj2EOZG6RCuiGxKKQm5uG0o78sv3e/7peP8fs3AW25er0+uqRH1JzWRfrqbBxb7AMZyHTFQKNKqCAIINEkE79oqHgAVTDw34toQvZe8N8Tt8LloJYhEkgMUmCLk4kwdJ63r7trYTp2+RUzHJ4djDSvQvAUTCS1NFYmaKKY8Wf10abNgiQqux01hw4VCigUjpmBEqwmRmGatGALAioUPyXNwBkEDdergsHQ37xpoBoAcmy8xa8G9Q+wp1UaoEZAWKyHwDrQKNaw0hNhqCeLIZE6NyOaX2guoCETQPQO7XqLCICneyKdDDykKs4giZibV376dbWfFseTAIdeSgpMi1do7K0im8jXoL8ePo9X1V5jYqNvpel9q72ue/6VSitWPJlZLfkV3l0FcbpOBTTDyfvptC6x4LpyxMNi1Fm9BS2tHuaEXMGtqAvQkpIgPqX6wzSYZsrz6L9BpdLUlD1OPWdNBYe/r4kON0yCP6ZXUnYufDM1hta89s1EHiH94r4OeX8Z69/f2zQajej9bHFjYcMztHLjIxv2GvdkUv026HdtoYxSWW0McYNVPOGT6Ip+NAsf1lyl3Ou4je15wQOWqGhY9s4gVJPlHBQZ9pcHinl7rzeUAD5OjvNU6hFe+YZ5HhaBtfU6fAvuhIoLLxdgbHDlqU41E+ZPU8pGcoddHXufJpQ6NFPfvt+W/oLW7WJbWEMOwR6UdoMFnL1QXX2awOHVV4JEci2Ap4OUG9uLihNDqPqtYtf6z53GQ/tnNUM06NMVbdefttOqppaKHhQIZoFK9gTXRRXiKBPCFr00y8WGo21HM692Z1HFNMKTNBtqSydfhaZadAuUB4SCb2MvKFoLOLmINDDJzobWRNh19He0lIY9myhj55DW/ZtZXcfCL4wNpT6s56tBVF7MPDmHqa8YgIGeJVYWQZdzNoyKVPMqfsiUwLkBs+6AI8d7rkDs3KuSCoE6Y4LLupcikzgBFfQjKLorspNHoypLRhg0wYyL8OVpmP67RoNQW0YVuXUms9toqpMX3jmzJzKmpDbeqaAzV+ezxfAEPfMieOukqGEkGzdpvobKWhGE9VBGjn6bn42+iwXzohRj1HMBQigKgQQFODWMme7vPyA7l8vl5S+kfuaXJ1PTSk9CgSF9YOBk167hEJ+u8gh/cMx++l/yX4gcjC7KK5jbkuz4kTYqqqruFQ7wsK7YdWvfAk8mpAw92XMC5hKC2pKTzzqkbW6ntvwt3Up3+jZuV+7U4sXPrJ8Hp2De4yKjD4RIII4ivfwVzewgSBNkNuWK4Ommovu+0xKdGfJ0xmae8N78MibZi032kcjgAEAGIFn0LALHEHhJtVR5/MfEt6UUPSftECh6c3f7EpHg8OwjxUmihfK6rRNml1AckjxaEpQNetXHw9X0fw/02YYIPXIRAHpIYalgDrUa+HxeNfj7anu9VIqWa3jHa+nMwMJXiuAb2Pfm/IU5QQRPxDSeGPnj3Oez3B+WyI0PcRWqangYRyCgTEaWVOhqCKq3wp6ok0ScioRrwxTBhO4obYFEmgIHmIu/pe5c3/YrbJUK0mYvu4bWU3ZZ3gs/R7EXK9igcGMkRFA9qIEV7dDVGUquVbpqkfdPK6/6Fm8uvx7Nns7SjDhrd1/eAiIIfV3+Kk8tXUAiImhL9fbgqOLwR5VQF885EkBWnzStAVEh04Bhy8HL8fxr8mMvgKidrOCGyAqJvSts5xLaAVE1MFgColDezAKiVH709Kkum/iAVEzZAFRMHCAqJVUbOxewbAComWk8s8/AaJc+YCom5Pq4bufOVdWYBUTJbw2w0OIIwO2RYQoF1rPzi2lEdizCG5Xl1mG67Oq4zkShTQQ4tttHGlYbFsmnMMc7nDlQxjJTrvZO6VU6EucmMXK0MjDMaGMjQajkle1aoUVfZ6uTrnY1zaDa6XQRbC4o1IqlDUaQ7NC2Nl5Vo2hVrUyMoDIWVUaXWQWYy0PHW5ZVQqUEKgseSQHaDHE2WwO/HmBIiRjC/Hs65e69NoColzWgTon2IiV9SwBUTdpq06wFRJ3YBqw38oCom8AqJKiyO6AyEP8AJIQ+bnyAi1thT9H5ttbtaVk2acnOceLtrr8W46x5DWlKN0u1zNZ1nHDHLqCU4NmY1ogsUGLI2IbW2gVFTQRKKMGFmhikeYVpySIwpgGiW1bU5WyUKIxGJHFCoCKwZTFJcc2ttB0tttY1hAopTalSrAqIULCBcWsEEENhLPsG06BaCClQHhMYsJTFA8/tfmw/vVe2F/Cn4Oe9T3Pr6YmRFTwedJ/Ne9hFhaNptI+6D/DLDKJur/bEfpC1GEkzIiq1TnQWJlTr6g1zeJLiWMgbkFgnr6ENMydK6I7QGN1vzJ/m/6fljJmBHsJW+JBfQvyJfnelsqjQyOdNMxbm/QVmFofmQz5nAfngnY8C+/2SbZZzCtDhD/EOvejv09h1pnrQccrptBQbGKCMljmLYjin94CSETRknQ9sNcVzUosj4OtJk9NQKZIpOIUd32A4sH4OAHRluGHCAMwy5KpeBRHlYsj3onCrFA9KMEXHlbE6lHmIx0w9oEK9dYTh3LNA2fYzDzg9WHGQBgZVYDK6JjdbpGWPxa6S9mpJpzkoLQqNJlJ4SrzbvXElQBb5kmKXFWClUgRMCFgsFj3xyxgSm1wuPh0hiek/YAkhFDUMo232kS7gEkIZQvZM4ETV08zzMamChogNLlz8hQVKq8Mpiz/bKoT4IDLe6+lLDBbLw4bTl9+D3bJEWZD5bCTAfnoEdCx/6lrc0cMJzVVC3Afk2GA4f+ABXIwhkjBMBJu1OwxIy/FeDsKn13z+iJbyz32z550v1k/B3Az13NJNfO1gxCH9AVEmkaelt2Os11t72d3oJRcK0DOUwrCFA49IJTGMYxgS0A6zek6pB4b6znhoMNaejPG5g2HOqFoil5wLg66Gx2XhdMA8zPhtDNBszud3ZToO3QbxlJSP7e7i1N+u0bKE/cPz3wGGPG+1AHdXaX6Uqr1rGFq9Y1Tpvc0Iw5CaQzEBrSR7zxKZ3U1RWkt3gSrwKCwiDYXrvj2q3AodHTWGkTOpg1Sg3PB2yylpKtCd2cGFs7ibIJkJVW0GtJimlIX0Zz6LpSDcBH/xK1kduyb3eVJVdnnJUkFOzUDJB1oO/2QA0GeQkjrvDo7uo5BPPAQl0pSRn8I9VBgN+nXwb1+hKkGDwWJg7RpVbiyeUhm6nVcjE9GpuLU1Qcf/aW4dI8ayHJRJqUSCRMiCM0a4KYXCjjnhYXBA1Qw3vz5QLzFJOQhg3FCNtBnArcaMPy7EFbLDbhI/cSJ+AjE5N+RtNkgprMjbbbFSTFR5cGo/AyZQLCuQF91ouSZK+Yi+QBgXAfZTwuAC1lBhxFp0jGU8yaB0PIBJCJc11775Ja+cShDBsYDARYg0+iqHzirfgAIyggk5XwLynzNp4wn+hYIFhiy+hrbzr6dOJ2IRtKfSfhBEDkpYIklw40giBA4Tyi9HDgIwEQEQUEEIYxIOj1fSA8U915kHuFuCYT9HqLHR3rlJfPQhQZFUuM1Ps2ASnP3lETTvsQZCS4D+I9p7YCIRGAgyFApSAiEhefE1KUXhyREAxSyIyQxSgiSBf+pMGxjBO5eW8eCDaXJAFy79YJq5W4x4SMwKgVHxT4urUBRT5QJIQfkQBB3wv6hOss0u1mAuC6qmQ/IUotQukBK5KbR1jPf0YG/1sBnQQkQNPUBJCHLDZQIH72IgKEQRodHb7iYVVzIvTBEEPcHr5YyNyRSk0dJJagCokTHJvkGGHEk5UYmwEx7W5cyaql+wRn0hjx0Df8Gl6BgpNvngtYJml/vpuTuAxSrxTZ6C3ya3sBsQTTQH0NKoINQDYJJiCbxnSWeV61odrZENnwOMLysF4DnS/LdgKqD1OmXJyIkx0GNMhvdfw3+oDTP03rIvRaNE0NptiBjY00P2oKH98G+5GqQc35zp4ZNHblr5PwVrzEXBH24yJAwHnAbS27wS6p6Yl87HDa5dGVrmpHcYgJIRmC00c9PCJzhc8AEkIpUGbOYpCKh3FnhhwnxjZdZ4o9OIZjUNQIGofbBAyCJP1owqEBuLhvY0IvaReHu+aMSarrCm0K/YZTETfKw7Zqa6zrv6/VnU48dgt/2gJIQzVgb4IFwlHEiFuw6r2jwy13kGmxGVIlxMSptKFKUpcoHRWwFiDBhIGsjO40QrkH1qxERE0/r+XtupuvI6MnOhqU2EcN0ojt8NK8p6IWHe8eXlhOnxjiuXVvn1dxCxz04izWa52bWqlBVBpikXWVrK0LG0s2KKcMEZHljcNgUFhYCRIIBpjYNRJkA44Ly7Np3M39OkHt7pJHKi3b46JvpCUQYQobSBpMBkbGNNhw4xjyrbqMTHlkXnAfJcgGMLu1e+MA2o7ANQGLPo+CB73pX5ZKelQcLKNtrQRZqYClsSqWyyR1WojILGIaFCGLMI55D+nILPaAfWMljNdCwWJA23DMU2SAgUIJKQ1OjN/19HJ9hsXby9uOBsbM+wIYMzcD9gt6Hdnf5W6ei3sURRERRjEQQNW5yJwz5IIaZzwuvRyMcXvc5OIZOAKKdIpaBQB6oVxNQYqCqV8h5kCpkoEEsUEEk1bTtNipZjpbiPh85BgCQ+JPEwGFFP/VmKuCrOFVZINjAVa1ERUpKAYetdqaPiAndbKZrpTTGGWRNIiUTCUmhVZFKQ5eA9o2cpkG0oUZkBQsjNCjiyFhgoT1boDuh5eQmGhrv7s8PP0Tbc47DqwRMBtF6MJORA0GJBDQCkpGfDw3uPg9k9Y0tthQigcPGkkoEPKAfR6Mno9cN90no8n2+3F1otuQUbUoTHJIZDbjHsAopJhNBwtjz5vrGHSMDivHDeNZKEyISychkJIlIZC45bExHBmFAUk+BA4wQrL7Uk5Ix6PdPvvb8bvhHVP2AJIR5kue3+cke2YQt4qDbcvA6TnyOq372qiVAkpzgh5gRjkjM08blP+kj4a2xTBkdYtaohopSNWgbEiUobETDld9R1L8LrlciTNgYR3+rd08qYd9GgUF5fumqhZDtVe75hVDY0iwIojHjQG/TCkJkQ0KSbktJKyV/GK94GCbebdLRHKGAnmmFTw8Rt1AcCpxNobnkk2MlW34k+lar0SEbhUF6t80WUC+3NHd3byjFlskJE7rP6wEkI330a5tjDN2wtxEYIzQUX3dOV9xoID7XvnnU7PUd8GRDlApEiy01VMhcthhG6mmNWlqDboGMhQttn54O0xFiYpqROUtsQZYQ+4HBIMiSHNHGCJGE4BoQHGAIiBvIpAnl4OeIlQqpSr3OgqSxhwpQiCLJOBhIrjCiJCeA4PEalpOBpEEssPQQ9R5vvekvrxKj7I22rJPYlH1ND1N7OGCyJD7Pi+VeoBJCICrUoWCPpAPizLNAY+ABO16yegySZZLs0rKkFIviDBGXkLQVNmR+osiZ4BwwWgx0zhJLweHPSuoNY+mkpzKJlVB6zbVFBDxTAGAG2yLCL+zqVMR7VjxtliH6KANQkBAW0BQw0aaePs+ViZRt1EVRHjj5RJz+8qlIGSB8l6YpV0OaZNJQ8p5nne2QaAitfPsYsYahCXmTliJ03HCwAwhVB8MsTeNVgFrG7uzgDFegh98jQRFZFIlIKsn/ABJCMs8FlcEhapW29z63PUOki0nAxkBCqu5nszv8h34VwuRMMsJ96AkBsXEKk6H4X4eM8sEi2MJjQDax47OGxZbjdH2DnY2i0uBsTBElCAabzIjOI7AAgBxF79X2AnI4rLDTAzyrPYxEUxrqUCfmKtZrKLix6sH3LZMAdjjfd9+Fzxgqe+rhOrcK6lEDobmSJGEQEywRCu71IbOTQVLEUEFwBRvCaC0B3ffOToZOg50emekVUU/afxMPcwW8L9laFiDBGFfhudp9Ds14Zn6rxnK0OIjik8JwVFFOPhlvRrec4vMXKNtHxYZnUeYPJDIycL1itsuHiuEFnLSs6eJ109POuDujw50vEXQ45OnoZ2hxmLu7xZeKNzUa8plOHClwYdMV0plhXxZZUOc4gkyrDfHx8w6uE6+7eed55TujEX8TVqQ73l3wk6Rt/E0MEUBKSMlBkqmwNi5q0e+rVU16xcpfQc3EHyDHe4KHdvviQjaCiwnkIqqqvKraqwolW5dFUfNzoPHK4crfy05uPhrdXEWlQIgopzE9u5JnUz4EC75cesDjcH1OmHX1zwYXXjlIJUlPrm3DKOvXAvK822xR8mEPTwYPxyRmFL8QRZJgYsakgN7XiXVxDRRPbQ5b7e3xN/AODTGguQdEzbv3HhOboayJRpElKInEs0qAneyaJJovSIHXihpXjqh9GJkNYsRCB7YkPkkaXJyACfoPTiuBerckHyASQjGoc6AFNNq6tSUKZ+sRGsH9A/iDrLRc8ewGL3vF3HOqGv32Or51E5Ski1ltp23SADtC4CnYOndG8evt3otyGYXlelGPUZx+TG0oVjBbONte3t2kpaY+d4x2JvfbwdMSj/EBJCJ6Uy9JOWbCa9mdKHEqLqmXWUJfWAkhFBZ2Ce05n57s7hXtHEBJEEofL859F9vemjrPHXXXJJ4SGCzrchoDRDXT1wpQdwCSEeqtrCqao7eKJmPxrDNeZmNQjeYMB88xCSEaGNSfzsOkLn/c4Po7o/QhU9PybJZ/LDhPant9/ub+Fv7bYo+Lxw4iOrA/8XckU4UJChMRZKA==')))

